/*
 * @lc app=leetcode.cn id=95 lang=cpp
 *
 * [95] 不同的二叉搜索树 II
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right)
        : val(x), left(left), right(right) {}
};

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n < 1) {
            return {nullptr};
        }
        return generateTrees(1, n);
    }

    // 生成区间为[left, right]的所有二叉搜索树
    vector<TreeNode*> generateTrees(int left, int right) {
        vector<TreeNode*> result;
        
        // 递归终止条件：区间为空
        if (left > right) {
            return {nullptr};
        }

        // 遍历所有可能的根节点
        for (int i = left; i <= right; i++) {
            // 生成所有可能的左右子树
            vector<TreeNode*> leftTrees = generateTrees(left, i - 1);
            vector<TreeNode*> rightTrees = generateTrees(i + 1, right);

            // 生成根节点，并拼接左右子树
            for (auto& left: leftTrees) {
                for (auto& right: rightTrees) {
                    TreeNode* root = new TreeNode(i);
                    root->left = left;
                    root->right = right;
                    result.push_back(root);
                }   
            }
        }
        
        return result;
    }
};
// @lc code=end

